\section{Problem 4}

\subsection*{Question a}
	
		Similarly to B-tree, the number of vertices in a $B^{+}$-tree of depth $d$ corresponds to the following parametrized summation :
		\begin{displaymath}
				n_v(d)  =  1 + \sum_{i = 0}^{d-1}(m+1)(q+1)^{i}
		\end{displaymath}
		where $n_v$ is the number of vertices, $m$ the number of records in the root vertex, $q$ the number of keys in other vertices. 
		
	Following the same reflexion as in 2.a (\ref{eq:nbvertclosed}), we found out :
		\begin{equation}
			n_v(d) = 1 + (m+1)\dfrac{1 - (q + 1)^{d}}{1-(q+1)}
		\end{equation}

	To find $i_{mem}$, we need to solve the following equation : 
	\begin{equation}
		n_v(i_{mem} - 1) \times pageSize \leq memorySize
	\end{equation}
	
	\begin{displaymath}
		\begin{array}{r c l}
		memorySize &\geq& (1 + (m+1)\dfrac{1 - (q + 1)^{i_{mem} - 1}}{1-(q+1)}) \times pageSize\\
		&&\\
		i_{mem} - 1&\leq & \dfrac{ln\left(q\times\dfrac{memorySize - pageSize}{pageSize(m + 1)} + 1\right)}{ln(q + 1)} \\
		&&\\
		i_{mem} - 1&\leq & \dfrac{ln\left(191.16\times\dfrac{2^{33} - 8192}{8192(1 + 1)} + 1\right)}{ln(191.16 + 1)}\\
		i_{mem} &\leq & 4,503567104
		\end{array}
	\end{displaymath}
	
	As $i_{mem}$ must be an integer, $i_{mem}$ is equal to $4$.
	
\subsection*{Question b}

With the following parameters found in 3.d :
	\begin{displaymath}
		\left\lbrace 
			\begin{array}{r c l}
			d&=d_{max}&= 5\\
			r&=r_{max}&= 21\\
			q&=191.16 &\\
			m&=1&\\
			\end{array}\right.
	\end{displaymath}
	disk accesses are required between levels $i_{mem} - 1 = 3$ and $d = 5$. Thus, the number of disk accesses is between $1$ and $2$ plus one, to reach the leaves level.
	
	The probability for a vertex not to be cached is :
		\begin{displaymath}
			\begin{array}{r c l}
				P &=& 1 - \dfrac{n_c}{n_{v_4}} \\
				n_c &=& \left(\dfrac{memorySize}{pageSize} - n_v(3)\right)\\
				&&\\
				&=& \left(\dfrac{2^{33}}{8192} - 74238.2512\right)\\
				&&\\
				&=& 974337.7488\\
				P &=& 1 - \dfrac{n_c}{(m + 1)\times(q + 1)^{3}}\\\\
				P &=& 1 - \dfrac{974337.75}{(2 + 1)\times(191.16 + 1)^{3}}\\\\
				P &=& 1 - 0.045771938\\
				P &=& 0.954228062
			\end{array}
		\end{displaymath}
	
	Thus, the number of disk accesses for a random record in this $B^{+}$-tree of depth $5$ \\is $2.954228062 \simeq 2.95$.
	
	
\subsection*{Question c}
	
	Following the same reflexion as in 4.a, we find:

	\begin{displaymath}
		\begin{array}{r c l}
		memorySize &\geq& (1 + (m+1)\dfrac{1 - (q + 1)^{i_{mem} - 1}}{1-(q+1)}) \times pageSize\\
		&&\\
		i_{mem} - 1&\leq & \dfrac{ln\left(q\times\dfrac{memorySize - pageSize}{pageSize(m + 1)} + 1\right)}{ln(q + 1)} \\
		&&\\
		i_{mem} - 1&\leq & \dfrac{ln\left(193.41\times\dfrac{2^{33} - 8192}{8192(193.41 + 1)} + 1\right)}{ln(193.41 + 1)}\\
		i_{mem} &\leq &3.629576322
		\end{array}
	\end{displaymath}
	
	As $i_{mem}$ must be an integer, $i_{mem}$ is equal to $3$.
	
\subsection*{Question d}

With the following parameters found in 3.d :
	\begin{displaymath}
		\left\lbrace 
			\begin{array}{r c l}
			d&=d_{min}&= 4\\
			r&=r_{max}&= 21\\
			q&= 193.41&\\
			m&= q &= 193.41\\
			\end{array}\right.
	\end{displaymath}
	disk accesses are required between levels $i_{mem} - 1 = 2$ and $d = 4$. Thus, the number of disk accesses is between $1$ and $2$ plus one, to reach the leaves level.
	
	The probability for a vertex not to be cached is :
		\begin{displaymath}
			\begin{array}{r c l}
				P &=& 1 - \dfrac{n_c}{n_{v_3}} \\
				n_c &=& \left(\dfrac{memorySize}{pageSize} - n_v(2)\right)\\\\
				&=& \left(\dfrac{2^{33}}{8192} - 37990,6581\right)\\\\
				&=& 1010585.3419\\
				P &=& 1 - \dfrac{n_c}{(m + 1)\times(q + 1)^{2}}\\\\
				P &=& 1 - \dfrac{1010585.34}{(193.41 + 1)\times(193.41 + 1)^{2}}\\\\
				P &=& 1 - 0.137536255\\
				P &=& 0.862463745 
			\end{array}
		\end{displaymath}
	
	Thus, the number of disk accesses for a random record in this $B^{+}$-tree of depth $4$ \\is $2.862463745 \simeq 2.86$.